/*
day372 
2020.9.3 
*/

#include<iostream>
#include<vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
		int tem=nums.front(),count=1;
		for(int i=1;i<nums.size();++i)
		{
			if(nums[i]!=tem)
			{
				count--;
				if(count<0)
				{
					tem=nums[i];
					count=1;
				}
			}
			else
			{
				count++;
			}
		}
		
		count=0;
		for(int i=0;i<nums.size();++i)
		{
			if(nums[i]==tem)
			{
				++count;
			}
		}
		
		return count>=nums.size()/2 ? tem : -1;
    }
};

int main()
{
	return 0;
 } 
